\section{Query Algorithms}
\label{sec:query}

By dividing an XML document into chunks, multiple partial trees are constructed.
The evaluation of queries applied to the original XML document, can be are
applied to partial trees and the evaluation on theses partial trees can be done
separately. The Overall Algorithm outlines the ``big picture'' of evaluating a query
on multiple partial trees. The query starts from the root of the XML tree. Note
that the root node corresponds to the root node of every partial tree, and they
are put into the lists for intermediate results (lines 1--2). Hereafter, the
loops by $p$ over $[0, P)$ are assumed to be executed in parallel. An XPath
query consists of one or more steps, and in our algorithm they are processed one
by one.  For each step, our algorithm calls a sub-algorithm based on its axis
(given later) and updates the intermediate results (line 4). Lines 6--9 will be
executed when a query has a predicate.  


\begin{figure}
	\centering
	\begin{tabular}{l}
		\hline
		\hline
		\makebox[.95\linewidth][l]{\textbf{Overall Algorithm} \textsc{Query}($\mathit{steps}$, $\INDEXSET{pt}$)} \\
		\hline
		\textbf{Input}:           $\mathit{steps}$: an XPath expression \\
		\phantom{\textbf{Input}:} $\INDEXSET{pt}$: an indexed set of partial trees \\
		\textbf{Output}: an indexed set of results of query \\
		\makebox[1em][r]{1:}\hspace{1 mm} \textbf{for} $p \in [0, P)$ \textbf{do} \\
		\makebox[1em][r]{2:}\hspace{4 mm}    $\mathit{ResultList}_p \leftarrow \{~ \mathit{pt}_p.\mathit{root} ~\}$ \\
		\makebox[1em][r]{3:}\hspace{1 mm} \textbf{for all} $\emph{step} \in \emph{steps}$ \textbf{do} \\
		\makebox[1em][r]{4:}\hspace{4 mm} $\INDEXSET{ResultList} \leftarrow \hbox{\textsc{Query}}\langle\mathit{step}.\mathit{axis}\rangle(\INDEXSET{pt}, \INDEXSET{ResultList}, \mathit{step}.\mathit{test})$ \\
		\makebox[1em][r]{5:}\hspace{4 mm}    \textbf{if} $step.predicate \neq \hbox{\textsc{null}}$ \textbf{then} \\
		\makebox[1em][r]{6:}\hspace{7 mm}       $\INDEXSET{PResultList} \leftarrow \hbox{\textsc{PreparePredicate}}(\INDEXSET{ResultList})$ \\
		\makebox[1em][r]{7:}\hspace{7 mm}       \textbf{for all} $\emph{pstep} \in \emph{step.predicate}$ \textbf{do} \\
		\makebox[1em][r]{8:}\hspace{10 mm}         $\INDEXSET{PResultList} \leftarrow  \hbox{\textsc{PQuery}}\langle\mathit{step}.\mathit{axis}\rangle(\INDEXSET{pt}, \INDEXSET{PResultList}, \mathit{pstep})$ \\
		\makebox[1em][r]{9:}\hspace{7 mm}       $\INDEXSET{ResultList} \leftarrow \hbox{\textsc{ProcessPredicate}}(\INDEXSET{PResultList})$ \\
		\makebox[1em][r]{10:}\hspace{1 mm} \textbf{return} $\INDEXSET{ResultList}$ \\
		\hline
	\end{tabular}
	\caption{The overall algorithm for processing XPath queries over partial trees}
	\label{fig:algQuery2}
\end{figure}

The number of partial trees is the same as the number of the chunks. In case the
number of partial trees is one, the whole original XML document is treated as a
chunk, so that only one partial tree is constructed to work standalone without
needing to make any change to its configuration. This is a valuable property of
partial tree, making partial tree easily portable under different hardware settings.


We use the two index sets to implement the functions in section 3. For
\texttt{child} axis, $\mathsf{getChild(x)}$ is implemented by a set of indices
as $ [ch[x], ch[x+1])$. For example, in Figure~\ref{fig:2arrays}, the index of
\Np{B}{6} is 2  and its children are in the range $\mathsf{getChild(2)} =
[ch[2], ch[2+1]) = [3, 6)$.  
For \texttt{descendant} axis, $\mathsf{isDescendant(x, y)}$ can be implemented
by $st[y] < st[x]$ $and$ $ed[x] < ed[y]$. For \texttt{parent} axis,
$\mathsf{getParent}(x)$ is implemented by $par[x]$. For example, the index of
\Np{B}{6}'s parent is $par[2] = 1$. Since a node in the original XML tree may be
split into two or more nodes on different partial trees. When such a node is
selected in a partial tree (e.g., \Nr{B}{6} on \PT1), the other corresponding
nodes (\Np{B}{6} on \PT2 and \Nl{B}{6} on \PT3) should also be selected to be
consistent. When an open node in the results is needed to share, we simply use
$start$ as index to notify other partial trees and let them to put the open
nodes with the same $start$ into the results nodes.  
We call this process share nodes. After processing \texttt{parent} axis, we need
share nodes. For \texttt{ancestor} axis, we implement it by repeated proceeding
from child to parent.

Without loss of generality, the discussion focuses on \texttt{following} and
\texttt{following} \texttt{-sibling} axes only (\texttt{preceding} and
\texttt{preceding-sibling} axes are just in opposite direction). For
\texttt{following} axis, it is relatively easy that we simply compare the $end$
index. We first select the node with the smallest $end$ index. Then, nodes with
$end$ index greater than the smallest one and match the name test are selected
as the results. For \texttt{following-sibling}, we need a two-phases query: the
local query phase and the remote query phase. In the local query phase, we
utilize the $\mathit{folsib}$ to select siblings on the local partial tree.
Then, we will ask a remote query if the parent node can have more segments on
the right (i.e., right open). In the remote query phase, we select children and
on the remote partial trees and merge them with their local results as final
results. Note that after processing these axes, sharing nodes is needed.

We exploit the algorithms proposed in \cite{HaMa16} (Algorithm~7 and 8) for predicate.
The key idea of these two algorithms are introduced as follows:
(1) create links that point to the nodes in the input lists,
(2) evaluate the steps within the predicate with these links,
(3) after the evaluation of all steps, we use the links 
to track back to the nodes in the input lists as final results.
